package com.zhang.study.chapter10;

public class Code01_LinkedListMid {

    public static class Node {
        public int value;
        public Node next;

        public Node(int data) {
            this.value = data;
        }
    }

    /**
     * 在单链表中找中点或者中点前面一个位置的点
     *
     * @param head 头节点
     * @return 若链表个数是奇数，则返回中点；若链表个数是偶数，则返回中点前面一个位置的点
     */
    public static Node midOrUpMidNode(Node head) {
        // 若链表头结点为空 直接返回头结点，
        // 若链表只有一个节点，直接返回头结点， 符合奇数情况
        // 若链表只有两个节点，直接返回头结点  符合偶数的情况
        if (head == null || head.next == null || head.next.next == null) {
            return head;
        }
        // 到这里说明链表最少有三个节点
        Node slow = head.next;
        Node fast = head.next.next;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    /**
     * 在单链表中找中点或者中点后面一个位置的点
     *
     * @param head 头节点
     * @return 若链表个数是奇数，则返回中点；若链表个数是偶数，则返回中点后面一个位置的点
     */
    public static Node midOrBackMidNode(Node head) {
        // 若链表头结点为空 直接返回头结点，
        // 若链表只有一个节点，直接返回头结点， 符合奇数情况
        // 若链表只有两个节点，直接返回头结点  符合偶数的情况
        if (head == null || head.next == null || head.next.next == null) {
            return head;
        }
        // 到这里说明链表最少有三个节点
        Node slow = head.next.next;
        Node fast = head.next.next;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }



    public static void main(String[] args) {
        Node test = null;
        test = new Node(0);
        test.next = new Node(1);
        test.next.next = new Node(2);
        test.next.next.next = new Node(3);
        test.next.next.next.next = new Node(4);
        test.next.next.next.next.next = new Node(5);
        test.next.next.next.next.next.next = new Node(6);
        test.next.next.next.next.next.next.next = new Node(7);
        test.next.next.next.next.next.next.next.next = new Node(8);
        test.next.next.next.next.next.next.next.next.next = new Node(9);

        System.out.println(midOrUpMidNode(test).value);
        System.out.println(midOrBackMidNode(test).value);


    }

}
